;; list operation --- append
(define (append list1 list2)
  (if (null? list1)
      list2
      (cons (car list1) (append (cdr list1) list2))))


;;Exercise 2.20
(define (is-same-parity? m n)
    (if (even? m)
	(if (even? n) 1 0)
	(if (odd? n) 1 0)))

(define nil '())

(define (same-parity x . z)
  (define (iter l z)
    (if (null? z)
	l
	(if (is-same-parity? x (car z))
	    (iter (cons (car z) l) (cdr z))))
  (iter (list x) z))


;; Exercise 2.21
(define (square-list items)
  (if (null? items)
      NIL
      (cons (square (car items)) 
	    (square-list (cdr items)))))

(define (square x) (* x x))

(define (square-list-map items)
  (map square items))

;; Exercise 2.29
(define (make-mobile left right)
  (list left right))

(define (make-branch length structure)
  (list length structure))

;; a
(define (left-branch m)
  (car m))

(define (right-branch m)
  (car (cdr m)))

(define (branch-length b)
  (car b))

(define (branch-structure b)
  (car (cdr b)))

(define mobile1 (make-mobile (make-branch 5 5) (make-branch 5 6)))
(define branch1 (make-branch 10 mobile1))
(define a-mobile (make-mobile branch1 branch1))

(define (total-weight m)
  (define (total-weight-2 b)
    (let ((len  (branch-length b))
	  (stru (branch-structure b)))
      (cond ((null? b) 0)
	    ((not (pair? stru)) (display stru) stru)
	    (total-weight stru))))
  (+ (total-weight-2 (left-branch m))
     (total-weight-2 (right-branch m))))

(display mobile1)
(total-weight mobile1)
(display a-mobile)
(total-weight a-mobile)

;; Exercise 2.30
(define (square-tree tree)
  (cond ((null? tree) nil)
	((not (pair? tree)) (square tree))
	(else (cons (square-tree (car tree))
		    (square-tree (cdr tree))))))

(define tree1
 (list 1
       (list 2 (list 3 4) 5)
       (list 6 7)))

(define (square-tree-map tree)
  (map (lambda (sub-tree)
	 (if (pair? sub-tree)
	     (square-tree-map sub-tree)
	     (square sub-tree)))
  tree))

;; Exercise 2.31
(define (square-tree-3 tree) (tree-map square tree))
(define (tree-map proc tree)
  (map (lambda (sub-tree)
	 (if (pair? sub-tree)
	     (tree-map proc sub-tree)
	     (proc sub-tree)))
       tree))

;; Exercise 2.32
;; The subsets of s can be devided into two groups,
;;   * those has the frist element, or (car s), and 
;;   * those not.
(define (subsets s)
  (if (null? s)
      (list nil)
      (let ((rest (subsets (cdr s))))
	(append rest (map (lambda (x) (cons (car s) x))
			  rest)))))
(subsets (list 1 2 3))

;; Seq Ops
(define (accumulate op init seq)
  (if (null? seq)
      init
      (op (car seq)
	  (accumulate op init (cdr seq)))))
(accumulate + 0 (list 1 2 3 4 5 6))
(define nil '())
(accumulate cons nil (list 1 2 3 4 5 6))

;; Exercise 2.33
(define (map-2 proc seq)
  (accumulate (lambda (x y) (cons (proc x) y) )
	      nil 
	      seq))
(map-2 (lambda (x) (+ x 1)) (list 1 2 3 4))
;; 这里的(lambda (x y) (cons (proc x) y))匿名函数，y的实参为
;; nil ---> ((proc 4), nil) or (5) ---> (4 5) ---> (3 4 5) ---> ( 2 3 4 5)

(define (append-2 seq1 seq2)
  (accumulate cons seq2 seq1))
(append-2 (list 1 2 3 4)
	  (list 5 6 7 8))

(define (length-2 seq)
  (accumulate (lambda (x y) (+ 1 y)) 0 seq))
(length-2 (list 1 2 3 4 5 6))
(length-2 (list 1 2 3 4 5))

(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms) 
		(+ this-coeff (* higher-terms x)))
	      0
	      coefficient-sequence))

(horner-eval 0 (list 1 1 1))
(horner-eval 2 (list 1 1 1))
(horner-eval 1 (list 1 2 3))

;; Exercise 2.35
(define (count-leaves-2 t)
  (accumulate (lambda (this-node total-leaves)
		(+ total-leaves
		   (cond ((null? this-node) 0)
			 ((not (pair? this-node)) 1)
			 (else (count-leaves-2 this-node)))))
	      0
	      t))
(define (count-leaves-3 t)
  (accumulate + 
	      0 
	      (map (lambda (node)
		     (if (pair? node)
			 ;;(count-leaves-3 (cdr t))
			 (count-leaves-3 node)
			 1)) t)))

(count-leaves-2 (list 1 (list 2 3) (list 4 5)))
(count-leaves-3 (list 1 (list 2 3) (list 4 5)))

;; Exercise 2.36
(define (accumulate-n op init seqs)
  (if (null? (car seqs)) ;; whether the first list is empty?
      nil
      (cons (accumulate op init (map car seqs))
	    (accumulate-n op init (map cdr seqs)))))

(define testlist (list (list 1 2 3) (list 4 5 6) (list 7 8 9) (list 10 11 12)))
(display testlist)
(accumulate-n + 0 testlist)
(map (lambda (x) (cdr x)) testlist)

;; Exercise 2.37
(define (dot-product v w)
  (accumulate + 0 (map * v w)))
(define (matrix-*-vector m v)
  (map (lambda (m-v) (dot-product m-v v))))
(define (transpose mat)
  (accumulate-n cons nil mat))
(define (matrix-*-matrix m n)
  (let ((cols (transpose n))
	(map (lambda (m-v) (matrix-*-vector cols m-v)) m))))
(define (matrix-*-matirx m n)
  (let ((n-cols (transpose n))
	(map (lambda (m-row) 
	       (map (lambda (n-col) (dot-product m-row n-col)) 
		    n-cols))
	 m))))

;; Exercise 2.38
;; (fold-right + 0 (list 1 2 3))
;; (((+ 3 0) 2) 1)
;; (fold-left + 0 (list 1 2 3))
;; 0 + 3 + 2 + 1 = 6
;; (fold-right / 1 (list 1 2 3))
;; 1/3/2/1 = 1/6
;; (fold-left / 1 (list 1 2 3))
;; 1/1/2/3 = 1/6
;; (fold-right list nil (list 1 2 3))
;; (((3) 2) 1)
;; (fold-left list nil (list 1 2 3))
;; (((1) 2) 3)
;; fold-right和fold-left的区别在于方向，设有(a b)
;; (op a (op init b)) fold-right
;; (op (op init a) b) fold-left
;; 如果上述两个式子相等的话，那么fold-right和fold-right的结果是相同的

;; Exercise 2.39
(define (reverse seq)
  (flod-right (lambda (x y) (cons y x)) nil seq))
(define (reverse seq)
  (fold-left (lambda (x y) (cons x y)) nil seq))

;; Exercise 2.40
(define (unique-pairs n)
  (flatmap (lambda (i)
	 (map (lambda (j) (cons i j))
	      (enumerate-interval 1 (- i 1))))
       (enumerate-interval 2 n)))

;; TEST unique-pair
(unique-pairs 3) ; -> ((2 1) (3 1) (3 2))
(unique-pairs 2) ; -> ((2 1))
(unique-pairs 1) ; -> ()	 
(unique-pairs 0) ; -> ()

(define (flatmap proc seq)
  (accumulate append '() (map proc seq)))

(define (enumerate-interval a b)
  (if (> a b)
      '()
      (cons a
	    (enumerate-interval (+ a 1) 

;; TEST enumerate-interval
;; (1 2 3 4 5)
(enumerate-interval 1 5)
;; (1)
(enumerate-interval 1 1)
;; ()
(enumerate-interval 1 0) 




;; Exercise 2.46
(define (make-vect cons))
(define (xcor-vect car))
(define (ycor-vect cdr))
(define (add-vect v1 v2)
  (let ((x1 (xcor-vect v1))
	(y1 (ycor-vect v1))
	(x2 (xcor-vect v2))
	(y2 (ycor-vect v2))
	(make-vect (+ x1 x2) (+ y1 y2)))))
(define (sub-vect v1 v2)
  (let ((x1 (xcor-vect v1))
	(y1 (ycor-vect v1))
	(x2 (xcor-vect v2))
	(y2 (ycor-vect v2))
	(make-vect (- x1 x2) (- y1 y2)))))
(define (scale-vect s v)
  (let ((x (xcor-vect v))
	(y (ycor-vect v))
	(make-vect (* s x) (* s y)))))

;; Exercise 2.47
(define (make-frame origin edge1 edge2)
  (list origin edge1 edge2))
(define (origin-frame frame)
  (car frame))
(define (edge1-frame frame)
  (car (cdr frame)))
(define (edge2-frame frame)
  (car (cdr (cdr frame))))

(define (make-frame origin edge1 edge2)
  (cons origin (cons edge1 edge2)))
(define (origin-frame frame)
  (car frame))
(define (edge1-frame frame)
  (car (cdr frame)))
(define (edge2-frame frame)
  (cdr (cdr frame)))
